#ifndef MSC_MEM_POOL_H
#define MSC_MEM_POOL_H

#include "vector.h"
#include "list.h"
#include "rbtree.h"
#include <stddef.h>


#ifndef MS_BLOCK_MINSIZE
#define MS_BLOCK_MINSIZE    4096
#elif MS_BLOCK_MINSIZE < 256
#undef MS_BLOCK_MINSIZE
#define MS_BLOCK_MINSIZE 256
#endif

#define msc_mpool_sizebit  (sizeof(size_t)*8-1)

//保存申请的内存资源链表
typedef struct ms_mpool_memory_s {
    struct ms_mpool_memory_s* prev;  
    struct ms_mpool_memory_s* next;
    unsigned char data[0];  //内存开始使用位置
} ms_mpool_memory_t, *ms_mpool_memory;

//保存分配的内存块
typedef struct ms_mpool_block_s{
    struct ms_mpool_block_s* prev;   //前面的块
    struct ms_mpool_block_s* next;   //后面的块
    size_t b_free : 1;
    size_t size : msc_mpool_sizebit;    //内存块大小
    unsigned char ptr[0];
}ms_mpool_block_t,*ms_mpool_block;

const size_t msc_mpool_block_headsize = sizeof(ms_mpool_block_t);
const size_t msc_mpool_alloc_minsize = sizeof(struct ms_rbtree_n);
const size_t msc_mpool_minfreesize = msc_mpool_block_headsize + msc_mpool_alloc_minsize;

const size_t block_max_size = ((size_t)1 << msc_mpool_sizebit) - msc_mpool_block_headsize - 1;

typedef struct ms_mpool_s {
    void*( *allocate)(void* self, size_t size);
    void ( *deallocate)(void* self, void *p);
    void*( *reallocate)(void* self, void *p, size_t size);
    size_t block_size;  //最小分配单元大小，其他都是该大小的倍数
    ms_mpool_memory mem_list;    //申请的内存链表
    struct ms_rbtree_n free_blocks[0];
    //struct ms_rbtree_n _;
}ms_mpool_t,*ms_mpool;

const size_t msc_mpool_headsize = sizeof(ms_mpool_t) + sizeof(struct ms_rbtree_n);

#define MS_BLOCK_INSERT(p, i) do {	\
    (i)->prev = p;                    \
    if ((p)->next) {                  \
        (i)->next = (p)->next;          \
        (p)->next->prev = i;          \
    }                               \
    (p)->next = i;                    \
} while(0)

#define MS_BLOCK_REMOVE(i) if ((i)->next) { (i)->next->prev = (i)->prev;}			\
	if ((i)->prev) {(i)->prev->next = (i)->next;} 

static inline ms_rbtree_p ms_mpool_from_block(ms_mpool_block p) {
	return (ms_rbtree_p)(p + 1);
}

static inline ms_mpool_block ms_mpool_to_block(void* p) {
	return (ms_mpool_block)p - 1;
}
static inline ms_rbtree_p ms_mpool_free_block(ms_mpool_block free_block) {
    ms_rbtree_p i = ms_mpool_from_block(free_block);
    i->key = free_block->size;
    return i;
}

static inline bool ms_mpool_insert_block(ms_rbtree_p t, ms_mpool_block block) {
    return ms_rbtree_insert(t, ms_mpool_free_block(block), true);
}

static inline void ms_mpool_remove_block(ms_rbtree_p t, ms_mpool_block block) {
    ms_rbtree_remove(t, ms_mpool_from_block(block));
}

static inline ms_mpool_block ms_mpool_cut_block(ms_mpool_block block, size_t size) {
    if (block->size >= size + msc_mpool_minfreesize) {
		ms_mpool_block sub = (ms_mpool_block)(block->ptr + size);
		memset(sub, 0, msc_mpool_block_headsize);
		MS_BLOCK_INSERT(block, sub);
		sub->size = block->size - size - msc_mpool_block_headsize;
		sub->b_free = 1;
		block->size = size;	
		return sub;
	}
	return NULL;
}

static inline void* ms_mpool_allocate(void* mp, size_t size) {
#ifdef _IF_NULL_
    if (!mp) return NULL;
#endif
    void* p = NULL;
    ms_mpool mpool = (ms_mpool)mp;
    ms_rbtree_p fp = mpool->free_blocks;
    if (!MS_RBTREE_EMPTY(fp))
        fp = ms_rbtree_lower_bound(mpool->free_blocks, size);
    if (fp != mpool->free_blocks){
        ms_mpool_block b = ms_mpool_to_block(fp);
        p = b->ptr;
        b->b_free = 0; //开始使用
        //删除fp
        ms_rbtree_remove(mpool->free_blocks, fp);
		if (NULL == b->prev) {//第一项最小分配msc_mpool_alloc_minsize，防止释放时不能插入到空闲树中
			size = size > msc_mpool_alloc_minsize ? size : msc_mpool_alloc_minsize;
		}
        ms_mpool_block new_free = ms_mpool_cut_block(b, size);
        if (new_free) {
            //插入new_free
            ms_mpool_insert_block(mpool->free_blocks, new_free);
        }
    } else {
        //分配一个新的空间
        size_t alloc_size = size + sizeof(ms_mpool_memory_t) + msc_mpool_block_headsize;
        if (alloc_size <= mpool->block_size) {
            alloc_size = mpool->block_size;
        } else {
            alloc_size = (alloc_size / mpool->block_size + 1)* mpool->block_size;
        }
        char* new_item = (char*)ms_malloc(alloc_size);
        if (new_item) {
            memset(new_item, 0, alloc_size);
            size_t res_size = alloc_size;
            ms_mpool_memory item = (ms_mpool_memory)new_item;
            res_size -= sizeof(ms_mpool_memory_t);
            MS_LIST_INSERT(mpool->mem_list, item);
      
            ms_mpool_block block = (ms_mpool_block)item->data;
            res_size -= msc_mpool_block_headsize;
            block->prev = block->next = NULL;
            block->b_free = 0;
            block->size = res_size;
			//第一项最小分配msc_mpool_alloc_minsize
            ms_mpool_block sub = ms_mpool_cut_block(block, size > msc_mpool_alloc_minsize ? size : msc_mpool_alloc_minsize);
            if (sub) {
                //free_blocks插入sub
                ms_mpool_insert_block(mpool->free_blocks, sub);
            }
            p = block->ptr;
        }
    }
    return p;
}

static inline void ms_mpool_deallocate(void* mp, void* p) {
#ifdef _IF_NULL_
    if (!mp || !p) return ;
#endif
    ms_mpool mpool = (ms_mpool)mp;
    ms_mpool_block block = ms_mpool_to_block(p);
    if (block->b_free) return ;
    block->b_free = 1;
	if (block->size < msc_mpool_alloc_minsize && !block->prev->b_free) {
		block->prev->size += msc_mpool_block_headsize + block->size;
		MS_BLOCK_REMOVE(block);
		return;
	}
    size_t new_size = block->size;
    if (block->next && block->next->b_free) {
        //合并后一个
        new_size += block->next->size + msc_mpool_block_headsize;
        ms_mpool_remove_block(mpool->free_blocks, block->next);
        MS_BLOCK_REMOVE(block->next);
    }
    if (block->prev && block->prev->b_free) {
        //合并前一个
        new_size = block->prev->size + block->size + msc_mpool_block_headsize;
        ms_mpool_remove_block(mpool->free_blocks, block->prev);
        MS_BLOCK_REMOVE(block);
        block = block->prev;
    }
    if (block->prev == block->next) {
        //为NULL，释放资源
        ms_mpool_memory item = (ms_mpool_memory)block-1;
        MS_LIST_REMOVE(item);
        ms_free(item);
    }
    else {
		block->size = new_size;
        ms_mpool_insert_block(mpool->free_blocks,block);
    }
}

static inline void* ms_mpool_reallocate(void* mp, void *p, size_t size) {
#ifdef _IF_NULL_
    if (!mp) return NULL;
#endif
    if (!p) {
       return ms_mpool_allocate(mp, size);
    }
    else if (0 == size) {
        ms_mpool_deallocate(mp, p);
        return ms_mpool_allocate(mp, 0);
    }
    ms_mpool_block block = ms_mpool_to_block(p);
    size_t has_size = block->size;
	int complete_block = 0; //等于2表示释放后会变成一个完整的空闲内存
    //首先判断邻居是否有空闲空间,如果有，合并这些碎片空间
    if (block->next) {
		if (block->next->b_free) {
			has_size += block->next->size + msc_mpool_block_headsize;
			if (NULL == block->next->next)
				++complete_block;
		}
    }
	else {
		++complete_block;
	}
    if (block->prev) {
		if (block->prev->b_free) {
			has_size += block->prev->size + msc_mpool_block_headsize;
			if (NULL == block->prev->prev)
				++complete_block;
		}
    }
	else {
		++complete_block;
	}
    
	size_t old_size = block->size < size ? block->size : size;
    void* new_p = NULL;
    if (has_size >= size) {
		if (complete_block < 2) {
			ms_mpool_deallocate(mp, p);
            new_p = ms_mpool_allocate(mp, size); //如果失败，程序逻辑必有问题
			if (new_p != p)
				memcpy(new_p, p, old_size);
		}
		else {
			//完整的块会被直接释放，所以不能先释放
			//组合成一块
			ms_mpool mpool = (ms_mpool)mp;		
            if (block->next) {
                ms_mpool_remove_block(mpool->free_blocks, block->next);
                MS_BLOCK_REMOVE(block->next);
			}
            if (block->prev) {
                ms_mpool_remove_block(mpool->free_blocks, block->prev);
                MS_BLOCK_REMOVE(block);
				block = block->prev;
			}
			block->prev = NULL;
			block->next = NULL;
			block->size = has_size;
			block->b_free = 0;
			if (block->ptr != p) {
				memcpy(block->ptr, p, old_size);
			}	
			ms_mpool_block sub = ms_mpool_cut_block(block, size > msc_mpool_alloc_minsize ? size : msc_mpool_alloc_minsize);
			if (sub) {
                ms_mpool_insert_block(mpool->free_blocks, sub);
			}
			new_p = block->ptr;
		}
    }
    else {
        new_p = ms_mpool_allocate(mp, size);
        if (new_p) {
            memcpy(new_p, p, old_size);
            ms_mpool_deallocate(mp, p);
        }
    }
    return new_p;
}

CPUBLIC ms_mpool ms_mpool_create(size_t block_size){
    if (block_size < MS_BLOCK_MINSIZE) {
        block_size = MS_BLOCK_MINSIZE;
    }
    void* p = ms_malloc(block_size);
    if (p) {
        memset(p, 0, block_size);
        char* ptr = (char*)p;
        ms_mpool_memory top = (ms_mpool_memory)ptr;
        top->prev = top->next = top;
        ptr += sizeof(ms_mpool_memory_t);

        ms_mpool_block head = (ms_mpool_block)ptr;
        ptr += msc_mpool_block_headsize;
        head->prev = NULL;
        head->size = msc_mpool_headsize;
        //
        ms_mpool mpool = (ms_mpool)ptr;
        ptr += msc_mpool_headsize;
        mpool->allocate = ms_mpool_allocate;
        mpool->deallocate = ms_mpool_deallocate;
        mpool->reallocate = ms_mpool_reallocate;
        mpool->block_size = block_size;
        mpool->mem_list = top;

        ms_mpool_block free_block = (ms_mpool_block)ptr;
        ptr += msc_mpool_block_headsize;
        free_block->prev = head;
        head->next = free_block;
        free_block->next = NULL;
        free_block->b_free = 1;
        free_block->size = block_size - (ptr - (char*)p);

        MS_RBTREE_INIT(mpool->free_blocks);
        ms_mpool_insert_block(mpool->free_blocks, free_block);
        return mpool;
    }
    return NULL;
}

CPUBLIC void ms_mpool_destory(ms_mpool mpool) {
#ifdef _IF_NULL_
    if (!mpool) return ;
#endif
    ms_free(mpool->free_blocks); //释放有序free_block占用空间
    ms_mpool_memory top = mpool->mem_list->next;
    while (top != mpool->mem_list) {
        ms_mpool_memory next = top->next;
        ms_free(top);
        top = next;
    }
    ms_free(mpool->mem_list);
}

CPUBLIC void ms_mpool_clear(ms_mpool mpool) {
#ifdef _IF_NULL_
    if (!mpool) return ;
#endif
    ms_mpool_memory top = mpool->mem_list->next;
    while (top != mpool->mem_list) {
        ms_mpool_memory next = top->next;
        ms_free(top);
        top = next;
    }
    mpool->mem_list->next = mpool->mem_list->prev = mpool->mem_list;
    //初始化最初的内存
    char* ptr = (char*)mpool;
    ptr += msc_mpool_headsize;
    ms_mpool_block free_block = (ms_mpool_block)ptr;
    MS_RBTREE_INIT(mpool->free_blocks);
    ms_mpool_insert_block(mpool->free_blocks, free_block);
}

CPUBLIC void* ms_mpool_malloc(ms_mpool mpool, size_t size) {
    return ms_mpool_allocate(mpool, size);
}

CPUBLIC void* ms_mpool_calloc(ms_mpool mpool, size_t size) {
    void* p = ms_mpool_allocate(mpool, size);
    if (p) {
        memset(p, 0, size);
    }
    return p;
}

CPUBLIC void ms_mpool_free(ms_mpool mpool, void* p) {
    ms_mpool_deallocate(mpool, p);
}

CPUBLIC void* ms_mpool_realloc(ms_mpool mpool, void* p, size_t size) {
    return ms_mpool_reallocate(mpool, p, size);
}

//内存池占用总内存
CPUBLIC size_t ms_mpool_total_size(ms_mpool mpool) {
#ifdef _IF_NULL_
    if (!mpool) return 0;
#endif
    size_t total = 0;
    ms_mpool_memory item = mpool->mem_list;
    do {
        total += sizeof(ms_mpool_memory_t);
        ms_mpool_block sub = (ms_mpool_block)(item + 1);
        while (sub) {
            total += msc_mpool_block_headsize + sub->size;
            sub = sub->next;
        }
        item = item->next;
    } while (item != mpool->mem_list);
	return total;
}
//应用内存
CPUBLIC size_t ms_mpool_user_size(ms_mpool mpool) {
#ifdef _IF_NULL_
    if (!mpool) return 0;
#endif
	size_t total = 0;
	ms_mpool_memory item = mpool->mem_list;
    do {
        ms_mpool_block sub = (ms_mpool_block)(item + 1);
        while (sub) {
            total += sub->size;
            sub = sub->next;
        }
        item = item->next;
    } while (item != mpool->mem_list);
	return total - msc_mpool_headsize;
}
static inline size_t ms_mpool_block_size(ms_rbtree_p t, ms_rbtree_p n) {
    size_t total = 0;
    if (t != n) {
        total += n->key;
        total += ms_mpool_block_size(t, n->left);
        total += ms_mpool_block_size(t, n->right);
    }
    return total;
}
//空闲内存
CPUBLIC size_t ms_mpool_free_size(ms_mpool mpool) {
#ifdef _IF_NULL_
    if (!mpool) return 0;
#endif
    size_t total = ms_mpool_block_size(mpool->free_blocks, MS_RBTREE_TOP(mpool->free_blocks));
	return total;
}
#endif // MSC_MEM_POOL_H
